Apprentissage par différences temporelles (Temporal-Difference - TD)¶
2. Prédiction par différences temporelles¶
2.5. Exemple d'illustration
Chaque jour, lorsque vous sortez du travail vous essayez de prédire combien de temps vous allez mettre pour rentrer à la maison. Lorsque vous quittez votre bureau, vous notez l'heure, le jour de la semaine, le temps qu'il fait, et n'importe quelle autre chose qui pourrait vous sembler révélatrice.
Prenons l'exemple du lundi où vous quittez le bureau à 18 heures et que vous estimez que le trajet du retour prendra 30 minutes. Quand vous arrivez à votre voiture à 18h05 vous vous apercevez qu'il commence à pleuvoir. Le trafic routier est souvent moins rapide lorsqu'il pleut, vous réestimez donc votre durée du parcours à partir de ce moment à 35 minutes soit un nouveau total de 40 minutes.
Cinq minutes plus tard vous sortez de l'autoroute et vous semblez avoir particulièrement bien roulé. Vous estimez donc que finalement votre trajet prendra au total 35 minutes.
Malheureusement, sur la route en sortie de l'autoroute vous vous retrouvez bloqué derrière un camion que vous ne pouvez pas doubler. Vous quittez la route que vous êtes en train de suivre à 18h40. Trois minutes plus tard vous êtes à la maison.
Le tableau ci-dessous synthétise votre trajet:
| État | Temps écoulé (minutes) |
Prédiction du temps restant (valeur d'état) |
Prédiction Temps total |
Temps pour terminer le parcours (Revenu Gt) |
Différence de temps entre les étapes (Rt+1) |
|---|---|---|---|---|---|
| Sortie du bureau, lundi 18h00 | 0 | 30 | 30 | 43 | 5 |
| Arrivée à la voiture, il pleut | 5 | 35 | 40 | 38 | 15 |
| Sortie de l'autoroute | 20 | 15 | 35 | 23 | 10 |
| Route en sortie de l'autoroute, camion | 30 | 10 | 40 | 13 | 10 |
| Arrivée sur la route de la maison | 40 | 3 | 43 | 3 | 3 |
| Arrivée à la maison | 43 | 0 | 43 | 0 | - |
Les récompenses dans cet exemple sont les temps écoulés entre chaque étape du voyage. Nous utilisons un facteur de remise $\gamma=1$, et donc le revenu $G_t$ pour chaque état correspond au temps actuel pour terminer le trajet depuis cet état (dernière colonne). La valeur de chaque état correspond à l'estimation du temps nécessaire pour rentrer à la maison depuis cet état (seconde colonne).
Illustration avec la méthode de Monte-Carlo
Une manière simple de visualiser une opération de type Monte-Carlo est d'afficher le temps total prédit (dernière colonne) au cours de la trajectoire. Les flèches rouges montrent les changements dans les prédictions qu'il faudrait réaliser avec la méthode à $\alpha$-constant. Ces flèches représentent les erreurs pour chaque état la cible (revenu actuel - temps actuel pour arriver à la maison) et l'ancienne estimation (temps prédit pour rentrer):
Par exemple, quand vous quittez l'autoroute vous estimez que le temps restant est de 15 min, mais en réalité cela prend 23 min. Avec la méthode de Monte-Carlo, l'erreur est donc de $G_t-V(S_t)=23-15=8$ min. Si par exemple le paramètre alpha vaut $\alpha=0.5$, cela ajusterait la prédiction du temps nécessaire pour rentrer de 4 min, soit une estimation au prochain état de $V(S_{t+1})=15+4=19$ min. À chaque état, ce changement ne peut se faire qu'après être rentré à la maison car il faut connaître les différents revenus $G_t$ pour chaque état $s$.
Illustration avec la méthode des différences temporelles
Est-il nécessaire d'attendre d'être rentré à la maison pour ajuster les valeurs ? Supposons qu'un autre jour vous estimez de nouveau que le temps de retour sera de 30 minutes mais que cette fois-ci le traffic sur l'autoroute est complètement bloqué. Vous êtes cette fois-ci encore sur l'autoroute 25 minutes après être sorti du travail. Vous estimez alors qu'il vous faudra encore 25 minutes supplémentaires pour rentrer, soit un total de 50 minutes.
Dans cette situation, pendant que vous attendiez sur l'autoroute, vous vous êtes rendu compte que votre estimation initiale de 30 minutes n'était pas possible et vous l'avez ajustée. C'est l'approche utilisée avec les différences temporelles.
Avec cette approche, chaque erreur qui ajuste la valeur des prédictions est proportionnelle au modifications apportées aux prédictions dans le temps:
Par exemple, lorsque vous quittez l'autoroute vous estimez que le temps restant est de 15 minutes. L'erreur est donc de $\left[ {{R_{t + 1}} + \gamma {V}\left( {{S_{t + 1}}} \right) - {V}\left( {{S_t}} \right)} \right]=10+10-15=5$ min si $\gamma=1$.
Si par exemple $\alpha=0.5$, cela ajusterai le prochain état en ajoutant 2,5 min à la prédiction, soit $V(S_{t+1})=15+2,5=17,5$ min.
